package leetcode_数组.leetcode_数组的遍历;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

// 第三大的数
public class _414 {
    public static void main(String[] args) {
        int[] nums = {9, 2, 4, 2, 5};
        System.out.println(thirdMax(new int[]{2, 2, 3, 1}));
    }

    public static int thirdMax(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0], nums[1]);
        }
        quickSort(nums, 0, nums.length - 1);
        return nums[2];
    }

    public static void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int start = left;
        int end = right;
        int flag = left;
        while (left < right) {
            while (left < right && nums[right] > nums[flag]) {
                right--;
            }
            while (left < right && nums[left] <= nums[flag]) {
                left++;
            }
            if (left < right) {
                swap(nums, right, left);
            }
        }
        swap(nums, flag, left);
        quickSort(nums, start, left - 1);
        quickSort(nums, left + 1, end);
    }

    public static void swap(int[] nums, int a, int b) {
        int tem = nums[a];
        nums[a] = nums[b];
        nums[b] = tem;
    }

    public static List<List<Integer>> largeGroupPositions(String s) {
        ArrayList<List<Integer>> ans = new ArrayList<>();
        int start = 0, i = 0;
        for (; i < s.length(); i++) {
            if (s.charAt(i) != s.charAt(start)) {
                if (i - start >= 3) {
                    ans.add(Arrays.asList(start, i - 1));
                }
                start = i;
            }
        }
        if (i - start >= 3) {
            ans.add(Arrays.asList(start, i - 1));
        }
        return ans;
    }

}
